package com.jiang.专题.动态规划.Q931;

import java.util.Arrays;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/26 22:54
 */
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j == 0) matrix[i][j] = Math.min(matrix[i - 1][j], matrix[i - 1][j + 1]) + matrix[i][j];
                else if (j == n - 1) matrix[i][j] = Math.min(matrix[i - 1][j], matrix[i - 1][j - 1]) + matrix[i][j];
                else matrix[i][j] = Math.min(Math.min(matrix[i - 1][j - 1], matrix[i - 1][j]), matrix[i - 1][j + 1]) + matrix[i][j];
            }
        }
        return Arrays.stream(matrix[n - 1]).min().getAsInt();
    }
}
